#include <stdio.h>

#define MEMORY_SIZE 8096
#define BLOCK_SIZE 32  // 每个内存块的大小

// 内存块结构体
typedef struct Block {
    size_t size;
    struct Block* next;
} Block;

// 内存池
char mem[MEMORY_SIZE];

// 内存分块链表的头指针
Block* freeList = NULL;

// 函数声明
void initializeMemory();
void umallocTest();
void ufree(void* ptr);
void* umalloc(size_t size);
void umerge();

int main() {
    initializeMemory();  // 初始化内存池
    umallocTest();       // 测试内存分配和释放
    return 0;
}

// 初始化内存池
void initializeMemory() {
    freeList = (Block*)mem;
    freeList->size = MEMORY_SIZE - sizeof(Block);
    freeList->next = NULL;
}

// 内存分配测试函数
void umallocTest() {
    // 分配内存
    void* ptr1 = umalloc(64);
    void* ptr2 = umalloc(128);
    void* ptr3 = umalloc(256);

    // 释放内存
    ufree(ptr1);
    ufree(ptr3);

    // 再次分配内存
    void* ptr4 = umalloc(64);
    void* ptr5 = umalloc(512);

    umerge();  // 碎片整理

    // 输出内存分配结果
    printf("Allocated memory blocks:\n");
    printf("ptr1: %p\n", ptr1);
    printf("ptr2: %p\n", ptr2);
    printf("ptr3: %p\n", ptr3);
    printf("ptr4: %p\n", ptr4);
    printf("ptr5: %p\n", ptr5);
}

// 自定义内存分配函数
void* umalloc(size_t size) {
    Block* prevBlock = NULL;
    Block* currentBlock = freeList;

    // 遍历链表查找合适大小的内存块
    while (currentBlock) {
        if (currentBlock->size >= size) {
            // 找到合适大小的内存块
            if (currentBlock->size > size + sizeof(Block)) {
                // 如果剩余空间足够大，将其拆分为两块
                Block* newBlock = (Block*)((char*)currentBlock + sizeof(Block) + size);
                newBlock->size = currentBlock->size - size - sizeof(Block);
                newBlock->next = currentBlock->next;
                currentBlock->size = size;
                currentBlock->next = newBlock;
            }

            if (prevBlock) {
                prevBlock->next = currentBlock->next;
            } else {
                freeList = currentBlock->next;
            }
            return (void*)((char*)currentBlock + sizeof(Block));
        }
        prevBlock = currentBlock;
        currentBlock = currentBlock->next;
    }

    return NULL;  // 没有足够的内存块
}

// 自定义内存释放函数
void ufree(void* ptr) {
    if (ptr == NULL) {
        return;
    }

    Block* block = (Block*)((char*)ptr - sizeof(Block));
    block->next = freeList;
    freeList = block;
}

// 自定义碎片整理函数
void umerge() {
    Block* currentBlock = freeList;
    while (currentBlock) {
        Block* nextBlock = currentBlock->next;
        if (nextBlock && (char*)currentBlock + sizeof(Block) + currentBlock->size == (char*)nextBlock) {
            // 合并相邻的内存块
            currentBlock->size += sizeof(Block) + nextBlock->size;
            currentBlock->next = nextBlock->next;
        } else {
            currentBlock = currentBlock->next;
        }
    }
}
